package number

import "strconv"

// https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xngt85/
// 算法: 递归
// 时间复杂度: O(n)
func FizzBuzz(n int) []string {
	f := NewFinder(n)
	f.recur()
	f.setNumber()
	return f.answer[1:]
}

type findFizzBuzz struct {
	n      int
	answer []string
}

// 主方法: 递归
// 剪枝思路: 在递归方法中增加 3/5 的数量
// 先遍历 3n * 5m 这种情况
// 然后遍历 3 的倍数，排除了前面之后的情况
func (f *findFizzBuzz) recur() {
	x, y := 1, 1
	for ; 3*x*5*y <= f.n; x++ {
		for ; 3*x*5*y <= f.n; y++ {
			f.answer[3*x*5*y] = "FizzBuzz"
		}
	}
	x = 3
	for x <= f.n {
		if f.answer[x] == "" {
			f.answer[x] = "Fizz"
		}
		x += 3
	}
	y = 5
	for y <= f.n {
		if f.answer[y] == "" {
			f.answer[y] = "Buzz"
		}
		y += 5
	}
}

func (f *findFizzBuzz) setNumber() {
	for index := 1; index <= f.n; index++ {
		if "" == f.answer[index] {
			f.answer[index] = strconv.Itoa(index)
		}
	}
}

func NewFinder(n int) *findFizzBuzz {
	f := findFizzBuzz{
		n:      n,
		answer: make([]string, n+1),
	}
	return &f
}
